package Sort;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    private final static Random RANDOM = new Random(System.currentTimeMillis());

    public static void main(String[] args) {
        int[] nums = {3, 10, 2, 5, 4};
        QuickSort solution = new QuickSort();
        int[] res = solution.sortArray(nums);
        System.out.println(Arrays.toString(res));
    }

    public int[] sortArray(int[] nums){
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void  quickSort(int[] arr, int left, int right){
        if(left < right){
            int pivotIndex = partition(arr, left, right);
            quickSort(arr, left, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, right);
        }
    }

    // 分区函数
    private int partition(int[] arr, int left, int right) {
        // // 随机选择一个 pivot，并放到末尾
        int pivotIndex = left + RANDOM.nextInt(right - left + 1); // 随机数作为基准值
        int pivot = arr[pivotIndex];
        swap(arr, pivotIndex, right);

        // 初始化为left表示左边还没有放置比 pivot 小的元素，所以下一个 < pivot 的元素应该放在 left 位置。
        int  storeIndex = left; // storeIndex指向比 pivot 小的元素的“下一个位置”指针

        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) { // 当前元素小于基准值，因此需要更新i，让i指到这个位置，且将该值其交换到左边，要保证i左边的数都是比pivot小的
                swap(arr, storeIndex, j);
                storeIndex++; // 表示下一个小于 pivot 的元素要放到下一个位置。
            }
        }

        // 遍历结束后，把pivot放到中间，因为storeIndex左边都是比pivot小的数，右边就是pivot最后应该在的位置
        swap(arr, storeIndex, right);
        return storeIndex;
    }

    // 交换
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
